﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Algorithms;

namespace Algorithms
{
    public class QuickSortStrategy : ISortingStrategy
    {
        public void Sort(Genome[] generation, double[] fitnessTable)
        {
            QuickSortGenerationPart(generation, fitnessTable, 0, fitnessTable.Length - 1);
        }

        private static void QuickSortGenerationPart(Genome[] generation, double[] fitnessTable, int start, int end)
        {
            // can we still continue?
            int pivotIndex = (start + end) / 2;
            double pivot = fitnessTable[pivotIndex];
            int leftIndex = start;
            int rightIndex = end;

            do
            {
                // Keep increasing the indexes as long as the path is sorted
                while (fitnessTable[leftIndex] < pivot && leftIndex < end)
                {
                    leftIndex++;
                }
                while (pivot < fitnessTable[rightIndex] && rightIndex > start)
                {
                    rightIndex--;
                }

                if (leftIndex <= rightIndex)
                {
                    Swap(generation, fitnessTable, leftIndex, rightIndex);

                    leftIndex++;
                    rightIndex--;
                }
            }
            while (leftIndex <= rightIndex);

            // Do we have subtrees?
            if (start < rightIndex)
            {
                QuickSortGenerationPart(generation, fitnessTable, start, rightIndex);
            }
            if (leftIndex < end)
            {
                QuickSortGenerationPart(generation, fitnessTable, leftIndex, end);
            }
        }

        private static void Swap(Genome[] generation, double[] fitnessTable, int leftIndex, int rightIndex)
        {
            Genome tempGeneration = generation[leftIndex];
            double tempFitness = fitnessTable[leftIndex];

            generation[leftIndex] = generation[rightIndex];
            fitnessTable[leftIndex] = fitnessTable[rightIndex];

            generation[rightIndex] = tempGeneration;
            fitnessTable[rightIndex] = tempFitness;
        }
    }
}
